package Sort;

import java.util.Arrays;

/**
 * @Author Fizz Pu
 * @Date 2021/3/16 下午2:28
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[] {1, 3, 3, -1};
        new HeapSort().headSort(arr, 0, arr.length - 1);
    }

    public void headSort(int[] arr, int left, int right){
        // 调成大顶堆, 自己实现或者利用priorityQueue
        // 第一个元素与最后一个元素交换
        // 前n-1个元素调成大顶堆
        build(arr, left, right);

        for (int i = right; i >= left; i--) {
            int swap = arr[i];
            arr[i] = arr[left];
            arr[left] = swap;
            siftDown(arr, left, i - 1);
        }

        System.out.println(Arrays.toString(arr));
    }

    private void build(int[] arr, int left, int right) {
        for (int i = right; i >= left; i--) {
            siftDown(arr, i, right);
        }
    }

    private void siftDown(int[] arr, int start, int end) {
        int parent = start;
        int leftChild;
        int rightChild;

        while ((leftChild = parent * 2 + 1) <= end) {
            int tmp = leftChild;

            if (leftChild < end) {
                rightChild = leftChild + 1;
                if (arr[rightChild] > arr[leftChild]) {
                    tmp = rightChild;
                }
            }

            if (arr[tmp] <= arr[parent]) {
                break;
            }

            int swap = arr[tmp];
            arr[tmp] = arr[parent];
            arr[parent] = swap;
            parent = tmp;
        }
    }
}
